java -Xmx8000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf -i /storage/chc-comp18-benchmarks/lia/chc-lia-0124.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-3d12b04 [2018-06-19 23:30:35,931 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-19 23:30:35,933 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-19 23:30:35,945 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-19 23:30:35,945 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-19 23:30:35,946 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-19 23:30:35,948 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-19 23:30:35,949 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-19 23:30:35,951 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-19 23:30:35,952 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-19 23:30:35,953 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-19 23:30:35,953 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-19 23:30:35,954 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-19 23:30:35,955 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-19 23:30:35,955 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-19 23:30:35,959 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-19 23:30:35,961 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-19 23:30:35,973 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-19 23:30:35,975 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-19 23:30:35,976 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-19 23:30:35,977 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-19 23:30:35,979 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-19 23:30:35,980 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-19 23:30:35,980 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-19 23:30:35,985 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-19 23:30:35,987 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-19 23:30:35,987 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-19 23:30:35,988 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-19 23:30:35,989 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-19 23:30:35,989 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-19 23:30:35,994 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-19 23:30:35,995 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-19 23:30:35,996 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-19 23:30:35,997 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-19 23:30:35,997 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-19 23:30:35,998 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf [2018-06-19 23:30:36,020 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-19 23:30:36,021 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-19 23:30:36,021 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-19 23:30:36,021 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-19 23:30:36,023 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-19 23:30:36,023 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-19 23:30:36,023 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-19 23:30:36,023 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-19 23:30:36,024 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-19 23:30:36,024 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-19 23:30:36,024 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-19 23:30:36,024 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-19 23:30:36,024 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-19 23:30:36,024 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-19 23:30:36,025 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-19 23:30:36,025 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-19 23:30:36,025 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-19 23:30:36,025 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-19 23:30:36,025 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-19 23:30:36,028 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-19 23:30:36,028 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-19 23:30:36,074 INFO ]: Repository-Root is: /tmp [2018-06-19 23:30:36,091 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-19 23:30:36,096 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-19 23:30:36,098 INFO ]: Initializing SmtParser... [2018-06-19 23:30:36,098 INFO ]: SmtParser initialized [2018-06-19 23:30:36,099 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp18-benchmarks/lia/chc-lia-0124.smt2 [2018-06-19 23:30:36,101 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-19 23:30:36,181 INFO ]: Executing SMT file /storage/chc-comp18-benchmarks/lia/chc-lia-0124.smt2 unknown [2018-06-19 23:30:36,428 INFO ]: Succesfully executed SMT file /storage/chc-comp18-benchmarks/lia/chc-lia-0124.smt2 [2018-06-19 23:30:36,432 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-19 23:30:36,438 INFO ]: Walking toolchain with 4 elements. [2018-06-19 23:30:36,439 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-19 23:30:36,439 INFO ]: Initializing ChcToBoogie... [2018-06-19 23:30:36,439 INFO ]: ChcToBoogie initialized [2018-06-19 23:30:36,442 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 19.06 11:30:36" (1/1) ... [2018-06-19 23:30:36,517 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 19.06 11:30:36 Unit [2018-06-19 23:30:36,517 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-19 23:30:36,518 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-19 23:30:36,518 INFO ]: Initializing Boogie Preprocessor... [2018-06-19 23:30:36,518 INFO ]: Boogie Preprocessor initialized [2018-06-19 23:30:36,539 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 19.06 11:30:36" (1/1) ... [2018-06-19 23:30:36,539 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 19.06 11:30:36" (1/1) ... [2018-06-19 23:30:36,564 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 19.06 11:30:36" (1/1) ... [2018-06-19 23:30:36,564 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 19.06 11:30:36" (1/1) ... [2018-06-19 23:30:36,570 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 19.06 11:30:36" (1/1) ... [2018-06-19 23:30:36,571 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 19.06 11:30:36" (1/1) ... [2018-06-19 23:30:36,572 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 19.06 11:30:36" (1/1) ... [2018-06-19 23:30:36,583 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-19 23:30:36,584 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-19 23:30:36,584 INFO ]: Initializing RCFGBuilder... [2018-06-19 23:30:36,584 INFO ]: RCFGBuilder initialized [2018-06-19 23:30:36,585 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 19.06 11:30:36" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2018-06-19 23:30:36,597 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-19 23:30:36,597 INFO ]: Found specification of procedure False [2018-06-19 23:30:36,597 INFO ]: Found implementation of procedure False [2018-06-19 23:30:36,597 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-19 23:30:36,597 INFO ]: Found specification of procedure state [2018-06-19 23:30:36,597 INFO ]: Found implementation of procedure state [2018-06-19 23:30:36,597 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-19 23:30:36,597 INFO ]: Found specification of procedure Ultimate.START [2018-06-19 23:30:36,597 INFO ]: Found implementation of procedure Ultimate.START Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-19 23:30:36,812 INFO ]: Using library mode [2018-06-19 23:30:36,813 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.06 11:30:36 BoogieIcfgContainer [2018-06-19 23:30:36,813 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-19 23:30:36,815 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-19 23:30:36,815 INFO ]: Initializing TraceAbstraction... [2018-06-19 23:30:36,820 INFO ]: TraceAbstraction initialized [2018-06-19 23:30:36,821 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 19.06 11:30:36" (1/3) ... [2018-06-19 23:30:36,821 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5f20b0c4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 19.06 11:30:36, skipping insertion in model container [2018-06-19 23:30:36,822 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 19.06 11:30:36" (2/3) ... [2018-06-19 23:30:36,822 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5f20b0c4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.06 11:30:36, skipping insertion in model container [2018-06-19 23:30:36,822 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.06 11:30:36" (3/3) ... [2018-06-19 23:30:36,827 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-19 23:30:36,835 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-19 23:30:36,848 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-19 23:30:36,894 INFO ]: Using default assertion order modulation [2018-06-19 23:30:36,895 INFO ]: Interprodecural is true [2018-06-19 23:30:36,895 INFO ]: Hoare is false [2018-06-19 23:30:36,895 INFO ]: Compute interpolants for FPandBP [2018-06-19 23:30:36,895 INFO ]: Backedges is TWOTRACK [2018-06-19 23:30:36,895 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-19 23:30:36,895 INFO ]: Difference is false [2018-06-19 23:30:36,895 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-19 23:30:36,895 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-19 23:30:36,912 INFO ]: Start isEmpty. Operand 13 states. [2018-06-19 23:30:36,931 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-19 23:30:36,931 INFO ]: Found error trace [2018-06-19 23:30:36,932 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-19 23:30:36,933 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-19 23:30:36,938 INFO ]: Analyzing trace with hash -683425083, now seen corresponding path program 1 times [2018-06-19 23:30:36,940 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-19 23:30:36,941 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-19 23:30:36,976 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-19 23:30:36,976 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-19 23:30:36,976 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-19 23:30:37,006 INFO ]: Conjunction of SSA is unsat [2018-06-19 23:30:37,090 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-19 23:30:37,092 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-19 23:30:37,093 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-19 23:30:37,094 INFO ]: Interpolant automaton has 4 states [2018-06-19 23:30:37,113 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-19 23:30:37,113 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-19 23:30:37,116 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-19 23:30:37,237 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-19 23:30:37,238 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-19 23:30:37,238 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-19 23:30:37,239 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-19 23:30:37,240 INFO ]: Finished accepts. some prefix is accepted. [2018-06-19 23:30:37,254 INFO ]: With dead ends: 13 [2018-06-19 23:30:37,254 INFO ]: Without dead ends: 13 [2018-06-19 23:30:37,256 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-19 23:30:37,276 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-19 23:30:37,305 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-19 23:30:37,306 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-19 23:30:37,306 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-19 23:30:37,307 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-19 23:30:37,307 INFO ]: Finished accepts. word is rejected. [2018-06-19 23:30:37,307 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-19 23:30:37,307 INFO ]: Interpolant automaton has 4 states. [2018-06-19 23:30:37,308 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-19 23:30:37,308 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-19 23:30:37,308 INFO ]: Found error trace [2018-06-19 23:30:37,309 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-19 23:30:37,309 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-19 23:30:37,309 INFO ]: Analyzing trace with hash 204343015, now seen corresponding path program 1 times [2018-06-19 23:30:37,309 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-19 23:30:37,309 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-19 23:30:37,310 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-19 23:30:37,310 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-19 23:30:37,310 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-19 23:30:37,370 INFO ]: Conjunction of SSA is unsat [2018-06-19 23:30:37,560 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-19 23:30:37,560 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-19 23:30:37,560 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-19 23:30:37,571 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-19 23:30:37,619 INFO ]: Conjunction of SSA is unsat [2018-06-19 23:30:37,629 INFO ]: Computing forward predicates... [2018-06-19 23:30:37,965 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-19 23:30:37,990 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-19 23:30:37,990 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 6 [2018-06-19 23:30:37,991 INFO ]: Interpolant automaton has 6 states [2018-06-19 23:30:37,991 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-19 23:30:37,991 INFO ]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2018-06-19 23:30:37,991 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 6 states. [2018-06-19 23:30:38,101 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-19 23:30:38,102 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-19 23:30:38,103 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-19 23:30:38,103 INFO ]: Start accepts. Automaton has 6 states. Word has length 13 [2018-06-19 23:30:38,103 INFO ]: Finished accepts. some prefix is accepted. [2018-06-19 23:30:38,104 INFO ]: With dead ends: 15 [2018-06-19 23:30:38,104 INFO ]: Without dead ends: 15 [2018-06-19 23:30:38,105 INFO ]: 0 DeclaredPredicates, 18 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2018-06-19 23:30:38,105 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-19 23:30:38,107 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-19 23:30:38,107 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-19 23:30:38,109 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-19 23:30:38,109 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-19 23:30:38,109 INFO ]: Finished accepts. word is rejected. [2018-06-19 23:30:38,109 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-19 23:30:38,109 INFO ]: Interpolant automaton has 6 states. [2018-06-19 23:30:38,110 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-19 23:30:38,110 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-19 23:30:38,110 INFO ]: Found error trace [2018-06-19 23:30:38,110 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-19 23:30:38,110 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-19 23:30:38,110 INFO ]: Analyzing trace with hash -1649658231, now seen corresponding path program 2 times [2018-06-19 23:30:38,110 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-19 23:30:38,110 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-19 23:30:38,111 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-19 23:30:38,111 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-19 23:30:38,111 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-19 23:30:38,180 INFO ]: Conjunction of SSA is unsat [2018-06-19 23:30:38,412 WARN ]: Spent 143.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-06-19 23:30:38,703 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-19 23:30:38,703 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-19 23:30:38,703 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-19 23:30:38,713 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-19 23:30:38,756 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-19 23:30:38,756 INFO ]: Conjunction of SSA is unsat [2018-06-19 23:30:38,759 INFO ]: Computing forward predicates... [2018-06-19 23:30:39,172 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-19 23:30:39,191 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-19 23:30:39,191 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 8 [2018-06-19 23:30:39,191 INFO ]: Interpolant automaton has 8 states [2018-06-19 23:30:39,192 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-19 23:30:39,192 INFO ]: CoverageRelationStatistics Valid=19, Invalid=37, Unknown=0, NotChecked=0, Total=56 [2018-06-19 23:30:39,192 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 8 states. [2018-06-19 23:30:39,714 WARN ]: Spent 338.00 ms on a formula simplification. DAG size of input: 18 DAG size of output: 18 [2018-06-19 23:30:39,743 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-19 23:30:39,743 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-19 23:30:39,744 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-19 23:30:39,744 INFO ]: Start accepts. Automaton has 8 states. Word has length 17 [2018-06-19 23:30:39,745 INFO ]: Finished accepts. some prefix is accepted. [2018-06-19 23:30:39,745 INFO ]: With dead ends: 17 [2018-06-19 23:30:39,745 INFO ]: Without dead ends: 17 [2018-06-19 23:30:39,746 INFO ]: 0 DeclaredPredicates, 26 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=31, Invalid=59, Unknown=0, NotChecked=0, Total=90 [2018-06-19 23:30:39,746 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-19 23:30:39,748 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-19 23:30:39,748 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-19 23:30:39,749 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-19 23:30:39,749 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-19 23:30:39,749 INFO ]: Finished accepts. word is rejected. [2018-06-19 23:30:39,749 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-19 23:30:39,749 INFO ]: Interpolant automaton has 8 states. [2018-06-19 23:30:39,749 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-19 23:30:39,750 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-19 23:30:39,750 INFO ]: Found error trace [2018-06-19 23:30:39,750 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-19 23:30:39,750 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-19 23:30:39,750 INFO ]: Analyzing trace with hash 2119922091, now seen corresponding path program 3 times [2018-06-19 23:30:39,750 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-19 23:30:39,750 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-19 23:30:39,751 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-19 23:30:39,751 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-19 23:30:39,751 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-19 23:30:39,787 INFO ]: Conjunction of SSA is unsat [2018-06-19 23:30:40,378 WARN ]: Spent 184.00 ms on a formula simplification that was a NOOP. DAG size: 13 [2018-06-19 23:30:40,388 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-19 23:30:40,388 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-19 23:30:40,388 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-19 23:30:40,401 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-19 23:30:40,451 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-19 23:30:40,451 INFO ]: Conjunction of SSA is unsat [2018-06-19 23:30:40,455 INFO ]: Computing forward predicates... [2018-06-19 23:30:40,654 WARN ]: Spent 151.00 ms on a formula simplification. DAG size of input: 22 DAG size of output: 18 [2018-06-19 23:30:40,834 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-19 23:30:40,863 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-19 23:30:40,863 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 12 [2018-06-19 23:30:40,863 INFO ]: Interpolant automaton has 12 states [2018-06-19 23:30:40,864 INFO ]: Constructing interpolant automaton starting with 12 interpolants. [2018-06-19 23:30:40,864 INFO ]: CoverageRelationStatistics Valid=32, Invalid=100, Unknown=0, NotChecked=0, Total=132 [2018-06-19 23:30:40,864 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 12 states. [2018-06-19 23:30:41,006 WARN ]: Spent 111.00 ms on a formula simplification. DAG size of input: 32 DAG size of output: 32 [2018-06-19 23:30:41,259 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-19 23:30:41,259 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-19 23:30:41,260 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-19 23:30:41,260 INFO ]: Start accepts. Automaton has 12 states. Word has length 21 [2018-06-19 23:30:41,260 INFO ]: Finished accepts. some prefix is accepted. [2018-06-19 23:30:41,261 INFO ]: With dead ends: 19 [2018-06-19 23:30:41,261 INFO ]: Without dead ends: 19 [2018-06-19 23:30:41,261 INFO ]: 0 DeclaredPredicates, 34 GetRequests, 19 SyntacticMatches, 1 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 20 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=69, Invalid=171, Unknown=0, NotChecked=0, Total=240 [2018-06-19 23:30:41,261 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-19 23:30:41,264 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-19 23:30:41,264 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-19 23:30:41,265 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-19 23:30:41,265 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 21 [2018-06-19 23:30:41,265 INFO ]: Finished accepts. word is rejected. [2018-06-19 23:30:41,265 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-19 23:30:41,265 INFO ]: Interpolant automaton has 12 states. [2018-06-19 23:30:41,265 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-19 23:30:41,266 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-19 23:30:41,266 INFO ]: Found error trace [2018-06-19 23:30:41,266 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-19 23:30:41,266 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-19 23:30:41,266 INFO ]: Analyzing trace with hash 1762711629, now seen corresponding path program 4 times [2018-06-19 23:30:41,267 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-19 23:30:41,267 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-19 23:30:41,267 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-19 23:30:41,267 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-19 23:30:41,267 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-19 23:30:41,303 INFO ]: Conjunction of SSA is unsat [2018-06-19 23:30:41,611 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-19 23:30:41,611 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-19 23:30:41,611 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-19 23:30:41,618 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-19 23:30:41,686 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-19 23:30:41,686 INFO ]: Conjunction of SSA is unsat [2018-06-19 23:30:41,690 INFO ]: Computing forward predicates... [2018-06-19 23:30:45,449 WARN ]: Spent 2.90 s on a formula simplification. DAG size of input: 581 DAG size of output: 39 [2018-06-19 23:30:46,373 WARN ]: Spent 148.00 ms on a formula simplification. DAG size of input: 7 DAG size of output: 2 [2018-06-19 23:30:46,398 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-19 23:30:46,429 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-19 23:30:46,429 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 15 [2018-06-19 23:30:46,429 INFO ]: Interpolant automaton has 15 states [2018-06-19 23:30:46,430 INFO ]: Constructing interpolant automaton starting with 15 interpolants. [2018-06-19 23:30:46,430 INFO ]: CoverageRelationStatistics Valid=34, Invalid=176, Unknown=0, NotChecked=0, Total=210 [2018-06-19 23:30:46,430 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 15 states. [2018-06-19 23:30:49,976 WARN ]: Spent 2.94 s on a formula simplification. DAG size of input: 61 DAG size of output: 41 [2018-06-19 23:30:50,262 WARN ]: Spent 147.00 ms on a formula simplification. DAG size of input: 59 DAG size of output: 25 [2018-06-19 23:30:50,534 WARN ]: Spent 254.00 ms on a formula simplification. DAG size of input: 62 DAG size of output: 32 [2018-06-19 23:30:50,853 WARN ]: Spent 301.00 ms on a formula simplification. DAG size of input: 62 DAG size of output: 30 [2018-06-19 23:30:50,875 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-19 23:30:50,875 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-19 23:30:50,876 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-19 23:30:50,876 INFO ]: Start accepts. Automaton has 15 states. Word has length 25 [2018-06-19 23:30:50,876 INFO ]: Finished accepts. some prefix is accepted. [2018-06-19 23:30:50,877 INFO ]: With dead ends: 21 [2018-06-19 23:30:50,877 INFO ]: Without dead ends: 21 [2018-06-19 23:30:50,877 INFO ]: 0 DeclaredPredicates, 42 GetRequests, 21 SyntacticMatches, 2 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 27 ImplicationChecksByTransitivity, 8.0s TimeCoverageRelationStatistics Valid=85, Invalid=335, Unknown=0, NotChecked=0, Total=420 [2018-06-19 23:30:50,877 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-19 23:30:50,880 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-19 23:30:50,880 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-19 23:30:50,881 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-19 23:30:50,881 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-19 23:30:50,881 INFO ]: Finished accepts. word is rejected. [2018-06-19 23:30:50,881 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-19 23:30:50,881 INFO ]: Interpolant automaton has 15 states. [2018-06-19 23:30:50,881 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-19 23:30:50,882 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-19 23:30:50,882 INFO ]: Found error trace [2018-06-19 23:30:50,882 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-19 23:30:50,882 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-19 23:30:50,882 INFO ]: Analyzing trace with hash 853117551, now seen corresponding path program 5 times [2018-06-19 23:30:50,882 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-19 23:30:50,882 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-19 23:30:50,883 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-19 23:30:50,883 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-19 23:30:50,883 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-19 23:30:50,946 INFO ]: Conjunction of SSA is unsat [2018-06-19 23:30:51,692 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-19 23:30:51,693 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-19 23:30:51,693 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-19 23:30:51,699 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-19 23:30:51,742 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-19 23:30:51,742 INFO ]: Conjunction of SSA is unsat [2018-06-19 23:30:51,746 INFO ]: Computing forward predicates... [2018-06-19 23:30:54,177 WARN ]: Spent 2.06 s on a formula simplification. DAG size of input: 37 DAG size of output: 25 [2018-06-19 23:30:54,494 WARN ]: Spent 100.00 ms on a formula simplification. DAG size of input: 29 DAG size of output: 25 [2018-06-19 23:30:54,957 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-19 23:30:54,976 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-19 23:30:54,976 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 19 [2018-06-19 23:30:54,976 INFO ]: Interpolant automaton has 19 states [2018-06-19 23:30:54,976 INFO ]: Constructing interpolant automaton starting with 19 interpolants. [2018-06-19 23:30:54,977 INFO ]: CoverageRelationStatistics Valid=50, Invalid=292, Unknown=0, NotChecked=0, Total=342 [2018-06-19 23:30:54,977 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 19 states. [2018-06-19 23:30:55,400 WARN ]: Spent 365.00 ms on a formula simplification. DAG size of input: 56 DAG size of output: 53 [2018-06-19 23:30:55,555 WARN ]: Spent 124.00 ms on a formula simplification. DAG size of input: 54 DAG size of output: 28 [2018-06-19 23:30:55,750 WARN ]: Spent 175.00 ms on a formula simplification. DAG size of input: 56 DAG size of output: 32 [2018-06-19 23:30:56,058 WARN ]: Spent 288.00 ms on a formula simplification. DAG size of input: 58 DAG size of output: 37 [2018-06-19 23:30:56,378 WARN ]: Spent 300.00 ms on a formula simplification. DAG size of input: 60 DAG size of output: 46 [2018-06-19 23:30:56,753 WARN ]: Spent 341.00 ms on a formula simplification. DAG size of input: 56 DAG size of output: 53 [2018-06-19 23:30:56,788 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-19 23:30:56,788 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-19 23:30:56,789 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-19 23:30:56,789 INFO ]: Start accepts. Automaton has 19 states. Word has length 29 [2018-06-19 23:30:56,789 INFO ]: Finished accepts. some prefix is accepted. [2018-06-19 23:30:56,789 INFO ]: With dead ends: 23 [2018-06-19 23:30:56,789 INFO ]: Without dead ends: 23 [2018-06-19 23:30:56,790 INFO ]: 0 DeclaredPredicates, 49 GetRequests, 24 SyntacticMatches, 1 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 52 ImplicationChecksByTransitivity, 4.9s TimeCoverageRelationStatistics Valid=137, Invalid=513, Unknown=0, NotChecked=0, Total=650 [2018-06-19 23:30:56,790 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-19 23:30:56,794 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-19 23:30:56,794 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-19 23:30:56,794 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-19 23:30:56,794 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 29 [2018-06-19 23:30:56,795 INFO ]: Finished accepts. word is rejected. [2018-06-19 23:30:56,795 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-19 23:30:56,795 INFO ]: Interpolant automaton has 19 states. [2018-06-19 23:30:56,795 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-19 23:30:56,796 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-19 23:30:56,796 INFO ]: Found error trace [2018-06-19 23:30:56,796 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-19 23:30:56,796 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-19 23:30:56,796 INFO ]: Analyzing trace with hash -1661294575, now seen corresponding path program 6 times [2018-06-19 23:30:56,796 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-19 23:30:56,796 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-19 23:30:56,798 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-19 23:30:56,798 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-19 23:30:56,798 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-19 23:30:56,848 INFO ]: Conjunction of SSA is unsat [2018-06-19 23:30:57,764 WARN ]: Spent 653.00 ms on a formula simplification that was a NOOP. DAG size: 21 [2018-06-19 23:30:58,145 WARN ]: Spent 305.00 ms on a formula simplification that was a NOOP. DAG size: 31 [2018-06-19 23:30:58,476 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-19 23:30:58,476 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-19 23:30:58,476 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-19 23:30:58,482 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-19 23:30:58,567 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-19 23:30:58,567 INFO ]: Conjunction of SSA is unsat [2018-06-19 23:30:58,573 INFO ]: Computing forward predicates... [2018-06-19 23:31:07,450 WARN ]: Spent 7.78 s on a formula simplification. DAG size of input: 1098 DAG size of output: 68 [2018-06-19 23:31:07,641 WARN ]: Spent 152.00 ms on a formula simplification. DAG size of input: 38 DAG size of output: 31 [2018-06-19 23:31:08,233 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-19 23:31:08,264 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-19 23:31:08,264 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 21 [2018-06-19 23:31:08,264 INFO ]: Interpolant automaton has 21 states [2018-06-19 23:31:08,264 INFO ]: Constructing interpolant automaton starting with 21 interpolants. [2018-06-19 23:31:08,265 INFO ]: CoverageRelationStatistics Valid=60, Invalid=360, Unknown=0, NotChecked=0, Total=420 [2018-06-19 23:31:08,265 INFO ]: Start difference. First operand 23 states and 24 transitions. Second operand 21 states. [2018-06-19 23:31:09,220 WARN ]: Spent 900.00 ms on a formula simplification. DAG size of input: 111 DAG size of output: 63 [2018-06-19 23:31:09,720 WARN ]: Spent 334.00 ms on a formula simplification. DAG size of input: 109 DAG size of output: 29 [2018-06-19 23:31:09,986 WARN ]: Spent 215.00 ms on a formula simplification. DAG size of input: 109 DAG size of output: 27 [2018-06-19 23:31:10,557 WARN ]: Spent 522.00 ms on a formula simplification. DAG size of input: 113 DAG size of output: 39 [2018-06-19 23:31:11,155 WARN ]: Spent 572.00 ms on a formula simplification. DAG size of input: 105 DAG size of output: 48 [2018-06-19 23:31:11,572 WARN ]: Spent 363.00 ms on a formula simplification. DAG size of input: 116 DAG size of output: 46 [2018-06-19 23:31:12,534 WARN ]: Spent 880.00 ms on a formula simplification. DAG size of input: 112 DAG size of output: 61 [2018-06-19 23:31:12,564 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-19 23:31:12,564 INFO ]: Finished difference Result 25 states and 26 transitions. [2018-06-19 23:31:12,565 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-19 23:31:12,565 INFO ]: Start accepts. Automaton has 21 states. Word has length 33 [2018-06-19 23:31:12,565 INFO ]: Finished accepts. some prefix is accepted. [2018-06-19 23:31:12,566 INFO ]: With dead ends: 25 [2018-06-19 23:31:12,566 INFO ]: Without dead ends: 25 [2018-06-19 23:31:12,566 INFO ]: 0 DeclaredPredicates, 55 GetRequests, 26 SyntacticMatches, 3 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 86 ImplicationChecksByTransitivity, 14.0s TimeCoverageRelationStatistics Valid=167, Invalid=589, Unknown=0, NotChecked=0, Total=756 [2018-06-19 23:31:12,566 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-19 23:31:12,568 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-06-19 23:31:12,568 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-19 23:31:12,570 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 26 transitions. [2018-06-19 23:31:12,570 INFO ]: Start accepts. Automaton has 25 states and 26 transitions. Word has length 33 [2018-06-19 23:31:12,571 INFO ]: Finished accepts. word is rejected. [2018-06-19 23:31:12,571 INFO ]: Abstraction has 25 states and 26 transitions. [2018-06-19 23:31:12,571 INFO ]: Interpolant automaton has 21 states. [2018-06-19 23:31:12,571 INFO ]: Start isEmpty. Operand 25 states and 26 transitions. [2018-06-19 23:31:12,572 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-19 23:31:12,572 INFO ]: Found error trace [2018-06-19 23:31:12,572 INFO ]: trace histogram [8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-19 23:31:12,572 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-19 23:31:12,572 INFO ]: Analyzing trace with hash -1494134477, now seen corresponding path program 7 times [2018-06-19 23:31:12,572 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-19 23:31:12,572 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-19 23:31:12,573 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-19 23:31:12,573 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-19 23:31:12,573 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-19 23:31:12,628 INFO ]: Conjunction of SSA is unsat [2018-06-19 23:31:13,417 INFO ]: Checked inductivity of 105 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-19 23:31:13,417 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-19 23:31:13,417 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-19 23:31:13,424 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-19 23:31:13,477 INFO ]: Conjunction of SSA is unsat [2018-06-19 23:31:13,483 INFO ]: Computing forward predicates... [2018-06-19 23:31:13,743 WARN ]: Spent 219.00 ms on a formula simplification. DAG size of input: 54 DAG size of output: 36 [2018-06-19 23:31:50,045 WARN ]: Spent 35.29 s on a formula simplification. DAG size of input: 1478 DAG size of output: 47 [2018-06-19 23:31:50,250 WARN ]: Spent 174.00 ms on a formula simplification. DAG size of input: 44 DAG size of output: 37 [2018-06-19 23:31:56,714 WARN ]: Spent 6.25 s on a formula simplification. DAG size of input: 105 DAG size of output: 32 [2018-06-19 23:31:57,965 WARN ]: Spent 859.00 ms on a formula simplification. DAG size of input: 29 DAG size of output: 26 [2018-06-19 23:31:59,698 WARN ]: Spent 192.00 ms on a formula simplification. DAG size of input: 67 DAG size of output: 27 [2018-06-19 23:32:00,005 INFO ]: Checked inductivity of 105 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-19 23:32:00,025 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-19 23:32:00,025 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 18] total 29 [2018-06-19 23:32:00,025 INFO ]: Interpolant automaton has 29 states [2018-06-19 23:32:00,025 INFO ]: Constructing interpolant automaton starting with 29 interpolants. [2018-06-19 23:32:00,026 INFO ]: CoverageRelationStatistics Valid=110, Invalid=702, Unknown=0, NotChecked=0, Total=812 [2018-06-19 23:32:00,026 INFO ]: Start difference. First operand 25 states and 26 transitions. Second operand 29 states. [2018-06-19 23:32:54,929 WARN ]: Spent 54.85 s on a formula simplification. DAG size of input: 130 DAG size of output: 106 [2018-06-19 23:32:55,209 WARN ]: Spent 230.00 ms on a formula simplification. DAG size of input: 120 DAG size of output: 37 [2018-06-19 23:33:25,232 WARN ]: Spent 29.99 s on a formula simplification. DAG size of input: 124 DAG size of output: 60 [2018-06-19 23:33:25,604 WARN ]: Spent 336.00 ms on a formula simplification. DAG size of input: 124 DAG size of output: 57 [2018-06-19 23:33:26,004 WARN ]: Spent 365.00 ms on a formula simplification. DAG size of input: 127 DAG size of output: 64 [2018-06-19 23:33:26,445 WARN ]: Spent 402.00 ms on a formula simplification. DAG size of input: 132 DAG size of output: 69 [2018-06-19 23:34:07,346 WARN ]: Spent 40.87 s on a formula simplification. DAG size of input: 127 DAG size of output: 68 [2018-06-19 23:35:05,488 WARN ]: Spent 58.10 s on a formula simplification. DAG size of input: 123 DAG size of output: 104 [2018-06-19 23:35:05,525 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-19 23:35:05,525 INFO ]: Finished difference Result 27 states and 28 transitions. [2018-06-19 23:35:05,525 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-19 23:35:05,525 INFO ]: Start accepts. Automaton has 29 states. Word has length 37 [2018-06-19 23:35:05,526 INFO ]: Finished accepts. some prefix is accepted. [2018-06-19 23:35:05,526 INFO ]: With dead ends: 27 [2018-06-19 23:35:05,526 INFO ]: Without dead ends: 27 [2018-06-19 23:35:05,527 INFO ]: 0 DeclaredPredicates, 62 GetRequests, 26 SyntacticMatches, 1 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 223 ImplicationChecksByTransitivity, 230.8s TimeCoverageRelationStatistics Valid=266, Invalid=1066, Unknown=0, NotChecked=0, Total=1332 [2018-06-19 23:35:05,527 INFO ]: Start minimizeSevpa. Operand 27 states. [2018-06-19 23:35:05,530 INFO ]: Finished minimizeSevpa. Reduced states from 27 to 27. [2018-06-19 23:35:05,530 INFO ]: Start removeUnreachable. Operand 27 states. [2018-06-19 23:35:05,531 INFO ]: Finished removeUnreachable. Reduced from 27 states to 27 states and 28 transitions. [2018-06-19 23:35:05,531 INFO ]: Start accepts. Automaton has 27 states and 28 transitions. Word has length 37 [2018-06-19 23:35:05,531 INFO ]: Finished accepts. word is rejected. [2018-06-19 23:35:05,531 INFO ]: Abstraction has 27 states and 28 transitions. [2018-06-19 23:35:05,531 INFO ]: Interpolant automaton has 29 states. [2018-06-19 23:35:05,532 INFO ]: Start isEmpty. Operand 27 states and 28 transitions. [2018-06-19 23:35:05,532 INFO ]: Finished isEmpty. Found accepting run of length 42 [2018-06-19 23:35:05,532 INFO ]: Found error trace [2018-06-19 23:35:05,533 INFO ]: trace histogram [9, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-19 23:35:05,533 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-19 23:35:05,533 INFO ]: Analyzing trace with hash 1618126293, now seen corresponding path program 8 times [2018-06-19 23:35:05,533 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-19 23:35:05,533 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-19 23:35:05,533 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-19 23:35:05,533 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-19 23:35:05,533 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-19 23:35:05,629 INFO ]: Conjunction of SSA is unsat [2018-06-19 23:35:05,880 WARN ]: Spent 118.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-19 23:35:06,467 WARN ]: Spent 531.00 ms on a formula simplification. DAG size of input: 31 DAG size of output: 29 [2018-06-19 23:35:06,583 WARN ]: Spent 109.00 ms on a formula simplification. DAG size of input: 39 DAG size of output: 37 Received shutdown request... [2018-06-19 23:35:06,708 WARN ]: Removed 2 from assertion stack [2018-06-19 23:35:06,709 WARN ]: Verification canceled [2018-06-19 23:35:06,712 WARN ]: Timeout [2018-06-19 23:35:06,712 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 19.06 11:35:06 BoogieIcfgContainer [2018-06-19 23:35:06,713 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-19 23:35:06,713 INFO ]: Toolchain (without parser) took 270280.35 ms. Allocated memory was 308.8 MB in the beginning and 698.4 MB in the end (delta: 389.5 MB). Free memory was 261.2 MB in the beginning and 642.9 MB in the end (delta: -381.7 MB). Peak memory consumption was 499.9 MB. Max. memory is 7.1 GB. [2018-06-19 23:35:06,714 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 308.8 MB. Free memory is still 273.3 MB. There was no memory consumed. Max. memory is 7.1 GB. [2018-06-19 23:35:06,714 INFO ]: ChcToBoogie took 78.44 ms. Allocated memory is still 308.8 MB. Free memory was 261.2 MB in the beginning and 259.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 7.1 GB. [2018-06-19 23:35:06,715 INFO ]: Boogie Preprocessor took 65.79 ms. Allocated memory is still 308.8 MB. Free memory was 259.2 MB in the beginning and 257.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 7.1 GB. [2018-06-19 23:35:06,715 INFO ]: RCFGBuilder took 229.25 ms. Allocated memory is still 308.8 MB. Free memory was 257.2 MB in the beginning and 247.3 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 7.1 GB. [2018-06-19 23:35:06,716 INFO ]: TraceAbstraction took 269897.57 ms. Allocated memory was 308.8 MB in the beginning and 698.4 MB in the end (delta: 389.5 MB). Free memory was 245.3 MB in the beginning and 642.9 MB in the end (delta: -397.6 MB). Peak memory consumption was 484.0 MB. Max. memory is 7.1 GB. [2018-06-19 23:35:06,718 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.07 ms. Allocated memory is still 308.8 MB. Free memory is still 273.3 MB. There was no memory consumed. Max. memory is 7.1 GB. * ChcToBoogie took 78.44 ms. Allocated memory is still 308.8 MB. Free memory was 261.2 MB in the beginning and 259.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 7.1 GB. * Boogie Preprocessor took 65.79 ms. Allocated memory is still 308.8 MB. Free memory was 259.2 MB in the beginning and 257.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 7.1 GB. * RCFGBuilder took 229.25 ms. Allocated memory is still 308.8 MB. Free memory was 257.2 MB in the beginning and 247.3 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 7.1 GB. * TraceAbstraction took 269897.57 ms. Allocated memory was 308.8 MB in the beginning and 698.4 MB in the end (delta: 389.5 MB). Free memory was 245.3 MB in the beginning and 642.9 MB in the end (delta: -397.6 MB). Peak memory consumption was 484.0 MB. Max. memory is 7.1 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was analyzing trace of length 42 with TraceHistMax 9, while InterpolatingTraceCheckCraig was constructing Craig interpolants, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 34. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 269.8s OverallTime, 9 OverallIterations, 9 TraceHistogramMax, 197.2s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 100 SDtfs, 229 SDslu, 505 SDs, 0 SdLazy, 434 SolverSat, 291 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 1.0s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 290 GetRequests, 150 SyntacticMatches, 8 SemanticMatches, 132 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 409 ImplicationChecksByTransitivity, 260.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=27occurred in iteration=8, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 8 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.6s SatisfiabilityAnalysisTime, 70.1s InterpolantComputationTime, 359 NumberOfCodeBlocks, 359 NumberOfCodeBlocksAsserted, 31 NumberOfCheckSat, 344 ConstructedInterpolants, 3 QuantifiedInterpolants, 7057224 SizeOfPredicates, 381 NumberOfNonLiveVariables, 1561 ConjunctsInSsa, 281 ConjunctsInUnsatCore, 15 InterpolantComputations, 1 PerfectInterpolantSequences, 168/616 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/chc-lia-0124.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-19_23-35-06-734.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/chc-lia-0124.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-19_23-35-06-734.csv Completed graceful shutdown